package now_coder.linked_list;

import xu.linkedlist.problems.ListNode;
import xu.linkedlist.problems.SinglyLinkedListUtil;

public class NC23 {

    public ListNode partition (ListNode head, int x) {
        if (head == null)
            return null;

        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);
        dummy1.next = head;
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;
        ListNode cur = head;

        while (cur != null){
            if (cur.val < x){
                ListNode tmp = cur.next;
                p1.next = cur.next;

                p2.next = cur;
                p2 = cur;
                cur.next = null;
                cur = tmp;
            }else {
                p1 = p1.next;
                cur = cur.next;
            }
        }

        p2.next = dummy1.next;
        return dummy2.next;
    }

    public static void main(String[] args) {
        ListNode head = SinglyLinkedListUtil.buildLinkedList(new int[]{1, 4, 3, 2, 5, 2});
        SinglyLinkedListUtil.printList(new NC23().partition(head, 0));

        head = SinglyLinkedListUtil.buildLinkedList(new int[]{1});
        SinglyLinkedListUtil.printList(new NC23().partition(head, 0));
    }

}
